package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Arrays;
import java.util.Scanner;

/*
进阶问题：
给定n个闭合的整数区间[ai, bi]和n个整数c1,c2,...,cn
编写一个程序：
输入
	第一行
		读取区间的数量 n
	剩下的n行
		读取它们的起点ai、终点bi、满足被命中的点的最小值ci
	(整数c1,c2,...,cn从标准输入)
	(1 <= n <= 50000)
	(0 <= ai <= bi <= 50000)
	(1 <= ci <= bi - ai + 1)

输出
	此数轴上，把所有线段都命中，最少需要几个点

Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
 */
public class c区间选点by贪心plus不均匀命中率 {
	public static void main(String[] args) {
		c区间选点by贪心plus不均匀命中率 test = new c区间选点by贪心plus不均匀命中率();
		test.useGreedyAlgorithm3();
	}
	
	/**
	 * 前置方法
	 */
	public void useGreedyAlgorithm3() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		Segment[] segments = new Segment[n];
		for (int i = 0; i < n; i++) {
			segments[i] = new Segment(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
		}
		Arrays.sort(segments);
		int res = GreedyAlgorithm3(segments, n);
		System.out.println(res);
	}
	
	/**
	 * 迭代形式
	 * @param segments
	 * @param n
	 * @return
	 */
	public int GreedyAlgorithm3(Segment[] segments, int n) {
		int max = segments[n - 1].terminate;//寻找数轴的最大值
		int[] axis = new int[max + 1];//生成数轴
		for (int i = 0; i < n; i++) {//遍历
			int start = segments[i].start;//线段起点
			int terminate = segments[i].terminate;//线段终点
			int currentCount = findCurrentCount(axis, start, terminate);//寻找当前线段，已经被打上的点的数量
			int reminder = segments[i].number - currentCount;//声明当前线段，现在需要的，新的点的数量
			while (reminder > 0) {
				if (axis[terminate] == 0) {
					axis[terminate] = 1;
					reminder--;
					terminate--;
				} else {
					terminate--;
				}
			}
		}
		return findCurrentCount(axis, 0, max);
	}
	
	/**
	 * 寻找当前线段上已经存在的点的数量
	 * @param axis
	 * @param start
	 * @param terminate
	 * @return
	 */
	public int findCurrentCount(int[] axis, int start, int terminate) {
		int sum = 0;
		for (int i = start; i <= terminate; i++) {
			sum += axis[i];
		}
		return sum;
	}
	
	/**
	 * 线段类
	 * @author wuqiu
	 */
	private class Segment implements Comparable<Segment> {
		int start;
		int terminate;
		int number;
		public Segment(int start, int terminate, int number) {
			this.start = start;
			this.terminate = terminate;
			this.number = number;
		}
		@Override
		public int compareTo(Segment o) {
			int x = this.terminate - o.terminate;
			if (x == 0) {
				return this.start - o.start;//这个题还是一样；谁减谁都可以
				//当this.t==o.t, 结果是线段长的在前面
			}
			return x;
		}
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	/**
	 * 运用树状数组
	 * 前置方法
	 */
	public void useGreedyAlgorithm4() {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		Segment[] segments = new Segment[n];
		for (int i = 0; i < n; i++) {
			segments[i] = new Segment(scanner.nextInt(), scanner.nextInt(), scanner.nextInt());
		}
		Arrays.sort(segments);
		int res = GreedyAlgorithm3(segments, n);
		System.out.println(res);
	}
	
	/**
	 * 迭代形式
	 * @param segments
	 * @param n
	 * @return
	 */
	public int GreedyAlgorithm4(Segment[] segments, int n) {
		int max = segments[n - 1].terminate;//寻找数轴的最大值
		int[] axis = new int[max + 1];//生成数轴
		int[] treeArr = new int[max + 2];
		for (int i = 0; i < n; i++) {//遍历
			int start = segments[i].start;//线段起点
			int terminate = segments[i].terminate;//线段终点
			int currentCount = sum(terminate + 1, treeArr, max + 1) - sum(start, treeArr, max + 1);//寻找当前线段，已经被打上的点的数量
			int reminder = segments[i].number - currentCount;//声明当前线段，现在需要的，新的点的数量
			while (reminder > 0) {
				if (axis[terminate] == 0) {
					axis[terminate] = 1;
					update(terminate + 1, 1, treeArr, max + 1);
					reminder--;
					terminate--;
				} else {
					terminate--;
				}
			}
		}
		return sum(max + 2, treeArr, max + 1);
	}
	
	/**
	 * 更新树状数组c，注意i是项数，不是下标，而是下标+1
	 * @param location
	 * @param delta
	 * @param treeArr
	 * @param n
	 */
	public void update(int location, int delta, int[] treeArr, int n) {
		for (; location <= n; location += lowbit(location)) {
			treeArr[location] += delta;
		}
	}
	
	/**
	 * 前i项和，注意：i不是下标
	 * @param location
	 * @param treeArr
	 * @param n
	 * @return
	 */
	public int sum(int location, int[] treeArr, int n) {
		int sum = 0;
		if (location > n) {
			location = n;
		}
		for (; location > 0; location -= lowbit(location)) {
			sum += treeArr[location];
		}
		return sum;
	}
	
	/**
	 * 它通过公式来得出k，其中k就是该值从末尾开始1的位置。
	   * 然后将其得出的结果加上x自身就可以得出当前节点的父亲节点的位置
	   * 或者是x减去其结果就可以得出上一个父亲节点的位置。
	   * 比如当前是6，二进制就是0110，k为2，那么6+2=8，C(8)则是C(6)的父亲节点的位置；
	   * 相反，6-2=4，则是C(6)的上一个父亲节点的位置。
	 * @param x
	 * @return
	 */
	public int lowbit(int x) {
		return x - (x & (x - 1));
	}
	
	
}
